package com.atguigu.kruskal;

import java.util.Arrays;

/**
 * @author RuiKnag
 * @create 2021-06-27-19:47
 */
/*
* 克鲁斯卡尔算法是用来计算加权连通图的最小生成树的算法
* 基本思想，按照权值从小到大选择n-1条边，并保证这n-1条边不构成回路
* 首先构造一个只含有n个点的森林，然后依照权值从小到大从连通图的中选择边加入到森林中，并使森林不产生回路，
* 直到森林变成一个回路
*
* 问题一：对图的所有边进行权值大小排序
* 问题二：将边添加到最小生成树中，判断是否生成了回路（难点 ）
*
* */
public class KruskalAlgroithm {

    public static void main(String[] args) {
        char[] vertexs={'A','B','C','D','E','F','G'};
        int[][] matrix={
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };
        KruskalAlgroithm kruskalAlgroithm = new KruskalAlgroithm(vertexs, matrix);
        kruskalAlgroithm.print();
//        EData[] edges = kruskalAlgroithm.getEdges(matrix);
//        System.out.println("排序之前的"+Arrays.toString(edges));
//        kruskalAlgroithm.sortEdges(edges);
//        System.out.println("排序之后的"+Arrays.toString(edges));
        kruskalAlgroithm.kruskal();

    }
    private int edgeNum;//边的数目
    private char[] vertexs;//顶点数组
    private int[][] matrix;//邻接矩阵
    //使用INF表示两个顶点不能联通
    private static final int INF=Integer.MAX_VALUE;
    //构造器

    public KruskalAlgroithm(char[] vertexs, int[][] matrix) {
        //初始化顶点数和边的个数
        int vlen=vertexs.length;
        //初始化顶点。复制拷贝的方式
        this.vertexs=new char[vlen];
        for (int i = 0; i < vlen; i++) {
            this.vertexs[i]=vertexs[i];
        }
        //初始化边，使用的是复制拷贝的方式
        this.matrix=new int[vlen][vlen];
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; j++) {
                this.matrix[i][j]=matrix[i][j];
            }
            
        }
        //统计边的数目
        for (int i = 0; i < vlen; i++) {
            for (int j = i+1; j < vlen; j++) {
                if(matrix[i][j]!=INF){
                    edgeNum++;
                }
            }

        }
    }
    //
    public void kruskal(){
        int index=0;//表示最后结果的数组索引
        int[] ends=new int[edgeNum];//用于保存已有的最小生成树中每个顶点在最小生成树的终点
        //创建结果数组，保存最小生成树
        EData[] rets = new EData[edgeNum];
        //获取图中所有边的集合，一共12边
        EData[] edges=getEdges();
        System.out.println("edges.length"+edges.length);
        sortEdges(edges);
        //遍历edges数组，将边添加到最小生成树时，判断准备加入的边是否形成了回路，如果没有就加入rets
        for (int i = 0; i < edgeNum; i++) {
            //获取第i条边的第一个顶点
            int p1=getPosition(edges[i].start);
            //获取第i条边的第二个顶点
            int p2=getPosition(edges[i].end);
            //获取p1在已有的最小生成树的终点
            int m=getEnd(ends,p1);
            int n=getEnd(ends,p2);
            //是否否成回路
            if(m!=n){
                ends[m]=n;
                rets[index++]=edges[i];//有一边加入到rets数组
            }

        }
        //统计打印最小生成树
        System.out.println("最小生成树"+Arrays.toString(rets));

    }


    public EData[] getEdges(){
        return  getEdges(matrix);
    }





    //打印邻接矩阵
    public void print(){
        System.out.println("邻接矩阵为\n");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d\t",matrix[i][j]);
            }
            System.out.println();
        }
    }
    //对边进行排序
    private void sortEdges(EData[] edges){
        for (int i = 0; i < edgeNum; i++) {
            for (int j = i+1; j < edgeNum; j++) {
                if(edges[i].weight>edges[j].weight){
                    EData temp=edges[i];
                    edges[i]=edges[j];
                    edges[j]=temp;
                }
            }
        }
    }
    //得到顶点对应的值
    private int getPosition(char ch){
        for (int i = 0; i < vertexs.length; i++) {
            if(vertexs[i]==ch){
                return i;
            }
        }
        return -1;
    }
    //获取图中的边
    private EData[] getEdges(int[][] matrix){
        int index=0;
        EData[] eData = new EData[edgeNum];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = i+1; j < matrix.length; j++) {
                if(matrix[i][j]!=INF){
                    eData[index++]=new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return eData;
    }
    //获取标为i的顶点的终点（），用于判断后面两个顶点的终点是否相同
    //数组就是记录的各个顶点对应的终点是哪一个 ends数组是在遍历过程中逐步形成的
    //i传入顶点对应的下标
    //返回的是
    private int getEnd(int[] ends,int i){
        while (ends[i]!=0){
            i=ends[i];
        }
        return i;
    }
}
//创建一个类 他的对象实例表示一条边
class EData{
    char start;//边的起点
    char end; //边的终点
    int weight;//边的权重

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
    //输出边的信息
    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}
